package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * 96. 不同的二叉搜索树
 * @author feizns
 * @since 2020/1/7
 */
public class NumTrees {

    public static void main(String[] args) {
        System.out.println(numTrees(4));
    }

    public static int numTrees(int n) {
        return numTrees(1, n);
    }

    private static Map<Integer, Integer> CACHE = new HashMap<>();

    public static int numTrees(int l, int r) {
        int hash = Objects.hash(l, r);
        Integer ret = CACHE.get(hash);
        if ( ret != null )
            return ret;
        if ( l == r )
            ret = 1;
        else if ( l < r ) {
            int sum = 0;
            for (int i = l; i <= r; i++) {
                int left = numTrees(l, i - 1);
                int right = numTrees(i + 1, r);
                if ( left != 0 && right != 0 )
                    sum += (left * right);
                else {
                    sum += left;
                    sum += right;
                }
            }
            ret = sum;
        } else {
            ret = 0;
        }
        CACHE.put(hash, ret);
        return ret;
    }

}
